/**
 * @file cfgym/103389/b/main
 * @brief 从 l 开始沿着 nxt 一路往右跳，要跳多少步才能跳到 > r 的地方？
 * @see https://codeforces.com/gym/103389/submission/157496561
 * @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
 * @copyright 2022
 * @date 5/17/2022 23:59:57
 **/

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i < (int)(b); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
char s[N];
int nxt[N][26];  // 保存了下一步能到达的位置
int f[N][20];    // 下一步能到达的最远的位置（倍增）
int pos[26];
int m, n;
int main() {
  // High rating and good luck!
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> m >> n;
  cin.ignore();
  cin.getline(s + 1, N);
  for (int i = 0; i < 26; ++i) nxt[n][i] = n + 1;  // 最远了

  for (int i = n; i >= 1; --i) {   // 倒序扫描 s 串
    if (!pos[s[i] - 'a'])          // 没有见到过这个字符
      nxt[i][s[i] - 'a'] = n + 1;  // 无穷远
    else                           // 见过了，存为见过的最远点
      nxt[i][s[i] - 'a'] = pos[s[i] - 'a'];
    pos[s[i] - 'a'] = i;           // 更新 pos 数组
    for (int j = 0; j < m; ++j) {  // 对于每个字母
      if (pos[j])                  // 更新 pos
        nxt[i - 1][j] = pos[j];
      else
        nxt[i - 1][j] = n + 1;
    }
  }
  // 初始化倍增数组的最低维
  for (int i = 0; i <= n; ++i) {
    int ma = 0;
    for (int j = 0; j < m; ++j) ma = max(ma, nxt[i][j]);
    f[i][0] = ma;
    for (int j = 0; j < 20; ++j) f[n + 1][j] = f[n][j] = n + 1;
  }
  // 建立倍增数组，能跳的最远的距离
  for (int j = 1; j < 20; ++j) {
    for (int i = 0; i <= n; ++i) {
      f[i][j] = f[f[i][j - 1]][j - 1];
    }
  }
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    int ans = 0;
    int now = l - 1;
    for (int i = 19; ~i; --i) {  // 使劲往远里跳
      if (f[now][i] <= r) {
        ans += (1 << i);
        now = f[now][i];
      }
    }
    cout << ans + 1 << endl;
  }
  return 0;
}
